#include <iostream>
#include <cstdio>

using namespace std;

class Matrix
{
    static const int MROW = 10,MCOL = 10,mod=10000;
    public:
    int row,col;
    int map[MROW][MCOL];
    Matrix(int row,int col)
    {
        this->row=row;
        this->col=col;
        init();
    }
    void init()
    {
        fill(map[0],map[0]+MROW*MCOL,0);
    }
    Matrix operator *(Matrix b)
    {
        Matrix t(row,b.col);
        for(int i=0;i<t.row;i++)
            for(int j=0;j<t.col;j++)
            {
                long long s =  0;
                for(int k=0;k<t.col;k++)
                {
                    s+=(long long)map[i][k]*b.map[k][j];
                }
                t.map[i][j] = s%mod;
            }

        return t;
    }
    Matrix pow(int n)
    {
        Matrix s(row,row);
        Matrix t  = *this;
        for(int i=0;i<row;i++)
            s.map[i][i]=1;
        while(n)
        {
            if(n&1)s = s * t;
            t = t * t;
            n>>=1;
        }
        return s;
    }
};

int main()
{
    int n;
    Matrix m1(1,2),m2(2,2);
    m1.map[0][0]=1;
    m2.map[0][0]=m2.map[0][1]=m2.map[1][0]=1;
    while(cin>>n)
    {
        if(n==-1) break;
        Matrix mt=m1*m2.pow(n);
        cout<<mt.map[0][1]<<endl;
    }
}
